Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding a longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and close relationships between Dijkstra's algorithm, weighted A*, and depth-first search.

Rankings, a special form of ordinal data, have received significant attention in the machine learning community as they arise in a number of important application domains, such as recommender systems, social voting and product placement platforms. Of particular importance are rankings of the form of linear orders (permutations) and partial rankings (weak orders), which are frequently obtained through conversion from ratings. One of the main processing tasks for rankings is rank aggregation, which often involves evaluating the median of a set of permutations or partial rankings under a suitably chosen distance function [2], [4], [7], [9], [11], [12], [16]. The median rank aggregation problem under the Kendall τ distance was introduced by Kemeny [11], and was proved to be NPhard by Bartholdi et al. [4]. A number of approximation algorithms for the problem have been described in [2], mostly pertaining to permutations; a corresponding PTAS (polynomial time approximation scheme) was proposed in [12]. In the context of partial ranking aggregation, known solutions include the results of [1], [10]. Median aggregation under other distance functions has received less attention, one notable exception being the Spearman rank aggregation problem [7], which is known to provide a constant approximation for Kendall τ aggregation using a polynomial time algorithm based on weighted bipartite matching [9]. We propose to investigate a broad new family of rank aggregation problems in which the median is replaced by a minmax type of function and where the rankings are grouped in classes.

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding a longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and close relationships between Dijkstra's algorithm, weighted A*, and depth-first search.